#include <stdio.h>
#include <string.h>

#define MAX_TASKS 8

typedef struct {
    char id;
    int duration;
    char prerequisites[10];
} Task;

int findIndexById(Task tasks[], int n, char id) {
    for (int i = 0; i < n; i++) {
        if (tasks[i].id == id)
            return i;
    }
    return -1;
}

void calculateCriticalPath(Task tasks[], int n) {
    int earliestStartTimes[MAX_TASKS] = {0};
    int latestCompletionTimes[MAX_TASKS];
    int completionTime = 0;

    // 计算最早开始时间
    for (int i = 0; i < n; i++) {
        int maxPreReqTime = 0;
        for (int j = 0; tasks[i].prerequisites[j] != '\0'; j++) {
            int preReqIndex = findIndexById(tasks, n, tasks[i].prerequisites[j]);
            if (preReqIndex != -1) {
                int preReqEnd = earliestStartTimes[preReqIndex] + tasks[preReqIndex].duration;
                if (preReqEnd > maxPreReqTime) {
                    maxPreReqTime = preReqEnd;
                }
            }
        }
        earliestStartTimes[i] = maxPreReqTime;
    }

    // 计算完成时间
    for (int i = 0; i < n; i++) {
        int taskCompletion = earliestStartTimes[i] + tasks[i].duration;
        if (taskCompletion > completionTime) {
            completionTime = taskCompletion;
        }
    }

    printf("The total duration of the project (Critical Path Length) is %d hours.\n", completionTime);
}

int main() {
    Task tasks[MAX_TASKS] = {
        {'A', 30, ""},
        {'B', 60, "A"},
        {'C', 45, "A"},
        {'D', 60, "B"},
        {'E', 60, "B"},
        {'F', 30, "DE"},
        {'G', 15, "C"},
        {'H', 0, "FG"}
    };

    calculateCriticalPath(tasks, 8);
    return 0;
}
